
header {
    package parser;
    import java.util.*;
}
options {
//    language="C";
}

/*
 [The "BSD licence"]
 Copyright (c) 2004 Terence Parr and Loring Craymer
 All rights reserved.

 Redistribution and use in source and binary forms, with or without
 modification, are permitted provided that the following conditions
 are met:
 1. Redistributions of source code must retain the above copyright
    notice, this list of conditions and the following disclaimer.
 2. Redistributions in binary form must reproduce the above copyright
    notice, this list of conditions and the following disclaimer in the
    documentation and/or other materials provided with the distribution.
 3. The name of the author may not be used to endorse or promote products
    derived from this software without specific prior written permission.

 THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
 IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
 OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
 IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
 INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
 NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
 DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
 THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
 (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
 THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
*/

/** Python 2.3.3 Grammar
 *
 *  Terence Parr and Loring Craymer
 *  February 2004
 *
 *  This grammar was derived automatically from the Python 2.3.3
 *  parser grammar to get a syntactically correct ANTLR grammar
 *  for Python.  Then Terence hand tweaked it to be semantically
 *  correct; i.e., removed lookahead issues etc...  It is LL(1)
 *  except for the (sometimes optional) trailing commas and semi-colons.
 *  It needs two symbols of lookahead in this case.
 *
 *  Starting with Loring's preliminary lexer for Python, I modified it
 *  to do my version of the whole nasty INDENT/DEDENT issue just so I
 *  could understand the problem better.  This grammar requires
 *  PythonTokenStream.java to work.  Also I used some rules from the
 *  semi-formal grammar on the web for Python (automatically
 *  translated to ANTLR format by an ANTLR grammar, naturally <grin>).
 *  The lexical rules for python are particularly nasty and it took me
 *  a long time to get it "right"; i.e., think about it in the proper
 *  way.  Resist changing the lexer unless you've used ANTLR a lot. ;)
 *
 *  I (Terence) tested this by running it on the jython-2.1/Lib
 *  directory of 40k lines of Python.
 *
 *  REQUIRES ANTLR 2.7.3rc3 at least (to resolve a FOLLOW bug).
 */

class PythonParser extends Parser;

options {
    k=2; // need for all the optional trailing semis and commas <blech>
    buildAST=false;
    ASTLabelType = "antlr.CommonAST";
}

tokens {
    PARAM;
    LIST;
    CALL;
    INDEX;
}

{
    Scope scope;
    ConstantTable constants = new ConstantTable();
    List<Function> functions = new ArrayList<Function>();
    List<ClassDefn> classes = new ArrayList<ClassDefn>();
    ExprList EMPTY_EXPR_LIST = new ExprList();
    Expr EMPTY_LIST = new ListExpr(EMPTY_EXPR_LIST);
    Expr EMPTY_DICT = new Dictionary(EMPTY_EXPR_LIST);
    Stack<LoopStmt> loops = new Stack<LoopStmt>();
    String file_name;
    int temps;

    Expr pack(ExprList list) {
        if (list.size() != 1 || list.trailingComma)
            return new Tuple(list);
        else
            return list.get(0);
    }

    void clean() {
        constants = new ConstantTable();
        functions = new ArrayList<Function>();
        classes = new ArrayList<ClassDefn>();

    }

    int name(Token n) {
        return NameTable.getIndex(n.getText());
    }

    public String getErrorMessage(RecognitionException e,
                                  String[] tokenNames)
    {
        System.err.println("Syntax Error: " + e.getMessage());
        System.exit(1);
        return "";
    }
    public String getTokenErrorDisplay(Token t) {
        return t.toString();
    }
}

// Start symbols for the grammar:
//	single_input is a single interactive statement;
//	file_input is a module or sequence of commands read from an input file;
//	eval_input is the input for the eval() and input() functions.
// NB: compound_stmt in single_input is followed by extra NEWLINE!

single_input returns [ BytecodeFile b ]
{
    b = null;
    Stmt s = null;
    scope = new TerminalScope();
    clean();
}
    : ( NEWLINE { s = new PassStmt(); }
	| s=simple_stmt
	| s=compound_stmt NEWLINE )
    { b = new BytecodeFile("stdin", constants, functions, classes, s); }
	;

file_input returns [ BytecodeFile b]
{
    Stmt s;
    StmtList sl = new StmtList();
    scope = new ModuleScope();
    b = null;
    clean();
}
    :   (NEWLINE | s=stmt { sl.add(s); } )* EOF { b = new BytecodeFile(file_name, constants, functions, classes, sl); }
	;

eval_input
{
    ExprList t;
}
    :   (NEWLINE)* t=testlist (NEWLINE)* EOF
	;

classdef returns [ Stmt s]
{
    ExprList t = EMPTY_EXPR_LIST;
    s = null;
    ClassDefn c;
    Scope enclosing;
}
    : "class" n:NAME (LPAREN t=testlist RPAREN)?
    { enclosing = scope; scope = new NewClassScope(name(n), enclosing); }
    COLON s=suite
    { c = new ClassDefn(name(n), t);
        Expr e = new MakeClass(name(n), t, s);
        scope = enclosing;
        Expr var = scope.name(name(n));
        s = var.assign(e);
        s.line(n);
        classes.add(c);
    }
	;

decorator returns [Decorator d]
{
    Parameters p = null;
    d = null;
}
: AT n:NAME (LPAREN p=arglist RPAREN)? NEWLINE
{
    d = new Decorator(scope.name(name(n)), p);
}
;

funcdef returns [Stmt s]
{
    List<Parameter2> p;
    Function f;
    FunctionScope fScope;
    Scope enclosing;
    s = null;
    Expr r = null;
    Stack<Decorator> decs = new Stack<Decorator>();
    Decorator d;
}
    : ( d=decorator { decs.push(d); } )*  "def"  n:NAME p=parameters
    { enclosing = scope; scope = fScope = new FunctionScope(p, scope); }
    ( ARROW r=expr)?
    COLON s = suite
    { scope = enclosing;
      Expr var = scope.name(name(n));
      f = new Function(name(n), p, s.returns(), fScope.getLocals(),
                       fScope.is_closure());
      Expr e = new LambdaExpr(p, functions.size(), r, fScope.is_closure());
      while(!decs.isEmpty()) {
          e = decs.pop().apply(e);
      }
      s = var.assign(e);
      s.line(n);
      functions.add(f);
    }
	;

parameters returns [List<Parameter2> p]
{
    p = new ArrayList<Parameter2>(0);
}
    :   LPAREN (p = varargslist)? RPAREN
	;

/* Parameters with types */

varargslist returns [List<Parameter2> l]
{
    l = new ArrayList<Parameter2>(0);
    Parameter2 p;
}
    :  p=parameter { l.add(p); } (options {greedy=true;}:COMMA p=parameter { l.add(p); } )*
       (COMMA
            ( STAR n1:NAME { l.add(new TupleParameter(name(n1))); } (COMMA DOUBLESTAR n2:NAME { l.add(new DictParameter(name(n2))); } )?
            | DOUBLESTAR n3:NAME { l.add(new DictParameter(name(n3))); }
            )?
       )?
    |   STAR n4:NAME { l.add(new TupleParameter(name(n4))); } (COMMA DOUBLESTAR n5:NAME { l.add(new DictParameter(name(n5))); } )?
    |   DOUBLESTAR n6:NAME { l.add(new DictParameter(name(n6))); }
    ;

parameter returns [ Parameter2 p ]
{
    Expr v = null;
    Expr t = null;
    p = null;
}
    :  n:NAME ( options {greedy=true;}:COLON t=expr )? (ASSIGN v=test)? { p = new Parameter2(name(n), t, v); }
    ;

stmt returns [Stmt c]
{
    c = null;
}
    : c=simple_stmt
	| c=compound_stmt
	;

simple_stmt returns [Stmt c]
{
    Stmt s, first;
    c = null;
}
    :   first=small_stmt { c = first; }
        (options {greedy=true;}:SEMI s=small_stmt {c = new StmtPair(c, s); } )*
        (SEMI)? n:NEWLINE { first.line(n); }
	;

small_stmt returns [Stmt c]
{
    c = null;
}
    : c=expr_stmt
	| c=del_stmt
	| c=pass_stmt
	| c=flow_stmt
	| c=import_stmt
	| c=from_stmt
	| c=global_stmt
	| c=assert_stmt
	;

expr_stmt returns [Stmt c]
{
    Expr e, e2;
    Expr r;
    String a;
    c = null;
}
	:
    e=expression (
    /* No RHS */ { c = scope.discard(e); }
    | a=augassign e2=expression { c = new AugAsgnStmt(e, a, e2); }
    | r=rhs { c = e.assign(r); }
    ) ;

rhs returns [Expr e]
{
    Expr r;
    e=null;
}
    :
    ASSIGN e=expression
    (  /* empty */
    | r=rhs { e = new AsgnExpr(e, r); }
	);

augassign returns [String opname]
{
    opname = null;
}
    : PLUSEQUAL{ opname = "iadd"; }
	| MINUSEQUAL{ opname = "isub"; }
	| STAREQUAL{ opname = "imul"; }
	| SLASHEQUAL{ opname = "itruediv"; }
	| PERCENTEQUAL{ opname = "imod"; }
	| AMPEREQUAL{ opname = "iand"; }
	| VBAREQUAL{ opname = "ior"; }
	| CIRCUMFLEXEQUAL{ opname = "ixor"; }
	| LEFTSHIFTEQUAL{ opname = "ilshift"; }
	| RIGHTSHIFTEQUAL{ opname = "irshift"; }
	| DOUBLESTAREQUAL{ opname = "ipow"; }
	| DOUBLESLASHEQUAL{ opname = "ifloordiv"; }
	;

del_stmt returns [ Stmt s ]
{
    ExprList e;
    s = null;
}
    : "del" e=exprlist  { s = new DeleteStmt(e); }
	;

pass_stmt returns [ Stmt s ]
{
    s = null;
}
    : "pass" { s = new PassStmt(); }
	;

flow_stmt returns [ Stmt s ]
{
    s = null;
}
    : s=break_stmt
	| s=continue_stmt
	| s=return_stmt
	| s=raise_stmt
	| s=yield_stmt
	;

break_stmt returns [Stmt s]
{
    s = null;
}
    : "break" { s = new BreakStmt(loops.peek());  }
	;

continue_stmt returns [Stmt s]
{
    s = null;
}
    : "continue" { s = new ContinueStmt(loops.peek()); }
	;

return_stmt returns [Stmt s]
{
    ExprList t;
    Expr r = Expr.NONE;
    s = null;
}
    : "return" ((t=testlist {r = pack(t); })? { s = new ReturnStmt(r, scope.protection_depth); }
    | "pass" { s = new ReturnStmt(null, scope.protection_depth); }
    )

	;

yield_stmt returns [Stmt s]
{
    ExprList t;
    s = null;
}
: "yield" t=testlist { s = new YieldStmt(pack(t), scope.protection_depth); }
	;

raise_stmt  returns [Stmt s]
{
    Expr t = null;
    s = null;
}
    : "raise" (t=test)? { s = new RaiseStmt(t); }
	;

import_stmt returns [ Stmt s]
{
    s = null;
    Stmt s2;
}
    :   "import" s=import_as_name (COMMA s2=import_as_name { s = new StmtPair(s, s2); } )*
	;

import_as_name returns [ Stmt s]
{
    s = null;
    int name = -1;
    StringBuffer c_name = new StringBuffer();
    String as_name;
}
    : n1:NAME { as_name = n1.getText(); c_name.append(as_name); }
    ( DOT n2:NAME { as_name = n2.getText(); c_name.append('.').append(as_name); } )*
    ("as" n:NAME { as_name = n.getText(); } )?
    { Expr e = constants.getString(c_name.toString());
    s = new ImportStmt(e, NameTable.getIndex(as_name)); }
	;

from_stmt returns [ Stmt s]
{
    s = null;
    FromStmt f;
    StringBuffer c_name = new StringBuffer();
    Expr e;
    int name, as_name;
}
    : "from" n1:NAME { c_name.append(n1.getText()); }
    ( DOT n2:NAME { c_name.append('.').append(n2.getText()); } )*
    { e = constants.getString(c_name.toString()); }
    "import"
        (
        STAR { s = new FromStar(e); } |
        n3:NAME { name = as_name = name(n3); } ("as" n4:NAME { as_name = name(n4); })?
        {  s = f = new FromStmt(e, name, as_name); }
        (COMMA
            n5:NAME { name = as_name = name(n5); } ("as" n6:NAME { as_name = name(n6);})?
            { f.addNames(name, as_name); }
        )*
        )
    ;

global_stmt returns [ Stmt s ]
{
    s = new PassStmt();
}
    : "global" n1:NAME { scope.global(name(n1)); } (COMMA n2:NAME { scope.global(name(n2)); })*
	;

assert_stmt returns [ Stmt s ]
{
    Expr t1, t2 = null;
    s = null;
}
    : "assert" t1=test (COMMA t2=test)? { s = new AssertStmt(t1, t2); }
	;


compound_stmt returns [ Stmt s ]
{
    s=null;
}
    : s=if_stmt
	| s=while_stmt
	| s=for_stmt
	| s=try_stmt
	| s=funcdef
	| s=classdef
	;

if_stmt returns [ IfStmt i ]
{
    Expr t;
    Stmt s;
    i = null;
}
    : x:"if" t=test COLON! s=suite { i = new IfStmt(t,s); i.line(x); }
    (e:"elif" t=test COLON s=suite { i.addIf(t, s, e.getLine()); } )*
    (e2:"else" COLON s=suite { s.line(e2); i.addElse(s); } )?
	;

while_stmt returns [ LoopStmt w ]
{
    Expr t;
    Stmt s;
    w = null;
}
    : x:"while" t=test  { w = new WhileStmt(t); loops.push(w); }
    COLON s=suite { w.setBody(s); }
//    ("else" COLON s=suite { w.addElse(s); } )?
    { loops.pop(); w.line(x); }
	;

for_stmt returns [ LoopStmt f]
{
    ExprList e, t;
    Stmt s;
    f = null;
    Expr temp;
}
    : x:"for" e=exprlist "in" t=testlist { temp = scope.name(NameTable.getIndex("" + ++temps));
                                           f = new ForStmt(pack(e),pack(t), temp);
                                           loops.push(f); }
    COLON s=suite { f.setBody(s); }
//    ("else" COLON s=suite { /* Quietly ignore for now */; })?
    { temps--; loops.pop(); f.line(x);  }
	;

try_stmt returns [ Stmt t ]
{
    Except e;
    Stmt s;
    t = null;
}
    :   x:"try" {scope.protection_depth++; } COLON t=suite  {scope.protection_depth--; }
        (   (e=except_clause COLON s=suite { t = new TryExcept(t, e, s); } )+
        ("else" COLON s=suite { ((TryExcept)t).addElse(s); } )?
        |   "finally" COLON s=suite { t = new TryFinally(t, s); }
        ) { t.line(x); }
	;
/*
except_clause: "except" (t1=test (COMMA t2=test)?)?
	;
*/
except_clause returns [ Except e ]
{
    ExprList t =null;
    e = null;
    Expr var = null;
}
    : "except" ( t=testlist ("as" n:NAME { var = scope.name(name(n)); } )? )? { e = new Except(t,var); }
    ;

suite returns [ Stmt s ]
{
    StmtList sl;
    s = null;
}
    : s=simple_stmt
	| NEWLINE INDENT { sl = new StmtList(); } (s=stmt { sl.add(s); })+ DEDENT { s = sl; }
	;


test returns [ Expr e ]
{
    Expr e2;
    e = null;
}
    : e=and_test ("or" e2=and_test { e = new OrExpr(e, e2); })*
	| e=lambdef
	;

and_test returns [ Expr e ]
{
    Expr e2;
    e = null;
}
	: e=not_test ("and" e2=not_test { e = new AndExpr(e, e2); })*
	;

not_test returns [ Expr e ]
{
    e = null;
}
	: "not" e=not_test { e = new NotExpr(e); }
	| e=membership
	;

membership returns  [ Expr e ]
{
    Expr e2;
    e = null;
}
    : e=identity (
        ("not" "in" e2=identity { e = new NotExpr(new InExpr(e, e2)); })
        |("in" e2=identity { e = new InExpr(e, e2); })
    )*
    ;

identity returns  [ Expr e ]
{
    Expr e2;
    e = null;
}
    : e=comparison (
        ("is" e2=comparison { e = new Identity(e, e2); })
        |("is" "not" e2=comparison { e = new NotExpr(new Identity(e, e2)); })
    )*
	;


comparison returns [ Expr e ]
{
    Expr e2, e3;
    ChainedComparison previous = null;
    String op, op2;
    Expr temp;
    e = null;
}
    : e=expr (
        /* empty */
        | ( op = comp_op e2=expr (
           /* empty */ { e = new Comparison(e, op, e2); }
           | op2 = comp_op e3 = expr {
                temp = scope.name(NameTable.getIndex("" + ++temps));
                e = new ChainedComparison(e, op, e2, temp);
                op = op2;
                e2 = e3;
            }
            ( op2 = comp_op e3 = expr {
                e = new AndExpr(e, new ChainedComparison(temp, op, e2, temp));
                op = op2;
                e2 = e3;
            }
            )*
            {
                e = new AndExpr(e, new Comparison(temp, op, e2));
                temps--;
            }
            )
          )
      )
      ;

comp_op returns [ String opname ]
{
    opname = null;
}
    : LESS { opname = "lt"; }
	|GREATER { opname = "gt"; }
	|EQUAL { opname = "eq"; }
	|GREATEREQUAL { opname = "ge"; }
	|LESSEQUAL { opname = "le"; }
	|ALT_NOTEQUAL { opname = "ne"; }
	|NOTEQUAL { opname = "ne"; }
	;

expr returns [ Expr e ]
{
    Expr e2;
    e = null;
}
    : e=xor_expr (VBAR e2=xor_expr { e = new Binary(e, "or_", e2); })*
	;

xor_expr returns [ Expr e ]
{
    Expr e2;
    e = null;
}
    : e=and_expr (CIRCUMFLEX e2=and_expr { e = new Binary(e, "xor", e2); })*
	;

and_expr returns [ Expr e ]
{
    Expr e2;
    e = null;
}
    : e=shift_expr (AMPER e2=shift_expr { e = new Binary(e, "and_", e2); })*
	;

shift_expr returns [ Expr e ]
{
    Expr e2;
    String op;
    e = null;
}
    : e=arith_expr ((LEFTSHIFT{op="lshift";}|RIGHTSHIFT{op="rshift";}) e2=arith_expr { e = new Binary(e, op, e2); })*
	;

arith_expr returns [ Expr e ]
{
    Expr e2;
    String op;
    e = null;
}
    : e=term ((PLUS {op="add";}|MINUS{op="sub";}) e2=term { e = new Binary(e, op, e2); })*
	;

term returns [ Expr e ]
{
    Expr e2;
    String op;
    e = null;
}
    : e=factor ((STAR{op="mul";} | SLASH{op="truediv";} | PERCENT{op="mod";} | DOUBLESLASH{op="floordiv";} ) e2=factor { e = new Binary(e, op, e2); })*
	;

factor returns [ Expr e ]
{
    String op;
    e = null;
}
	: (PLUS{op="pos";}
       |MINUS{op=null;}
       |TILDE{op="invert";}
      ) e=factor { if (op == null)
                    e = e.negate();
                   else
                    e = new Unary(op, e); }
	| e=power
	;

power returns [ Expr e ]
{
    Expr e2;
    e = null;
}
   	:  e=primary (options {greedy=true;}:DOUBLESTAR e2=factor { e = new Binary(e, "pow", e2); })?
	;

primary returns [ Expr e ]
{
    Parameters p;
    ExprList l;
    Expr s;
    e = null;
}
    :  e=atom (
        ( { p = Parameters.EMPTY; } LPAREN (p=arglist)? RPAREN { e = new Call(e, p); }
//        | LBRACK s:subscriptlist RBRACK { e = index(e, s); }
        | LBRACK s=subscript RBRACK { e = new Index(e, s); }  /* Replaced subscriptlist with subscript */
        | DOT n:NAME { e = new MemberExpr(e, name(n)); }
        | DOLLAR x:NAME { e = new SpecialExpr(e, name(x)); }
        | QUESTION y:NAME { e = new HasSpecialExpr(e, name(y)); }
        ) )*
    ;

atom returns [ Expr e ]
{
    ExprList x= EMPTY_EXPR_LIST;
    PythonString str;
    e = null;
}
    : LPAREN (x=testlist)? RPAREN { e = pack(x); }
	| LBRACK (e=listmaker | { e = EMPTY_LIST; } ) RBRACK
	| LCURLY (e=dictmaker | { e = EMPTY_DICT; } ) RCURLY
//	| BACKQUOTE t=testlist BACKQUOTE
	| n:NAME { e = scope.name(name(n)); }
	| i:INT  { e = constants.getInt(i); }
    | l:LONGINT { e = constants.getLong(l); }
    | f:FLOAT { e = constants.getFloat(f); }
    | c:COMPLEX { e = constants.getComplex(c); }
	| { str = new PythonString(); } (s:STRING { str.append(s.getText()); } )+ { e = constants.getString(str.toString()); }
    | "None" { e = Expr.NONE; }
    | "True" { e = Expr.TRUE; }
    | "False" { e = Expr.FALSE; }
    | DOLLAR q:NAME LPAREN (x=testlist)? RPAREN { e = new LowLevelExpr(q.getText(), x); }
	;

listmaker returns [ Expr e ]
{
    ExprList l;
    Expr t, temp;
    Stmt lf;
    e = null;
}
    : t = test
    ( (
        { temp = scope.name(NameTable.getIndex("" + ++temps)); }
        lf = list_for[ new AppendStmt(temp, t) ]
        { temps--; e = new ListFor(lf, temp); }   )
    |
    { l = new ExprList(); l.add(t); } (options {greedy=true;}:COMMA t=test { l.add(t); } )* { e = new ListExpr(l); } ) (COMMA)?
	;

lambdef returns [ Expr f ]
{
    List<Parameter2> p = new ArrayList<Parameter2>();
    Expr e;
    Function fn;
    f = null;
    Scope enclosing;
    FunctionScope ls;
}
    : l:"lambda" (p = simpleargslist)? COLON
    { enclosing = scope; scope = ls = new FunctionScope(p, scope); }
    e = test
    { Stmt ret = new ReturnStmt(e, 0);
      scope = enclosing;
      f = new LambdaExpr(p, functions.size(), null,ls.is_closure());
      int ln = NameTable.getIndex("lambda");
      int[] names = ls.getLocals();
      ret.line(l);
      fn = new Function(ln, p, ret, names, ls.is_closure());
      functions.add(fn); }
	;

simpleargslist returns [List<Parameter2> l]
{
    l = new ArrayList<Parameter2>(0);
}
    :  n1:NAME { l.add(new Parameter2(name(n1), null, null)); }
       (options {greedy=true;}:COMMA n2:NAME { l.add(new Parameter2(name(n2), null, null)); } )*
       (COMMA)?
    ;

/*
subscriptlist returns SliceList
    :  subscript (options {greedy=true;}:COMMA subscript)* (COMMA)?
	;
*/
subscript returns [ Expr s ]
{
    Expr t2 = null;
    Expr t3 = null;
    s = null;
}
	: s=test (COLON (t2=test)? (t3=sliceop)?  { s = new Slice(s, t2, t3); }  )?
//    | DOT DOT DOT
    | COLON (t2=test)? (t3=sliceop)?  { s = new Slice(null, t2, t3); }
    ;

sliceop returns [ Expr t ]
{
    t = null;
}
: COLON (t=test)?
	;

exprlist returns [ ExprList el ]
{
    Expr e;
    el = new ExprList();
}
    :   e=expr { el.add(e); } (options {greedy=true;}:COMMA e=expr { el.add(e); } )* (COMMA { el.trailingComma = true; })?
	;

expression returns [ Expr t ]
{
    t = null;
    ExprList el = new ExprList();
}
    :   t=test { el.add(t); }
        (options {greedy=true;}:COMMA  t=test { el.add(t); }
            (options {greedy=true;}:COMMA t=test { el.add(t); } )*
        { t = new Tuple(el); }
        )?
        (options {greedy=true;}:COMMA { el.trailingComma = true; })?
     {
        t = pack(el);
     }
    ;

testlist returns [ ExprList el ]
{
    Expr t;
    el = new ExprList();
}
    :   t=test { el.add(t); } (options {greedy=true;}:COMMA t=test { el.add(t); } )*
        (options {greedy=true;}:COMMA { el.trailingComma = true; } )?
    ;

dictmaker returns  [ Expr e ]
{
    Expr t;
    ExprList el = new ExprList();
    e = null;
}
    :   t=test { el.add(t); }
        (
        COLON t=test { el.add(t); }
        (options {greedy=true;}:COMMA t=test { el.add(t); } COLON t=test { el.add(t); } )* (COMMA)?
        {
            e = new Dictionary(el);
        }
        )
    ;

named_param returns [ NamedParam p ]
{
    Expr t;
    p = null;
}
    :
    n:NAME ASSIGN t = test
    {
        p = new NamedParam(constants.getString(n.getText()), t);
    }
    ;

/** Replace complicated argument syntax with simpler one  */
arglist returns [ Parameters p ]
{
    Expr t;
    Expr s=null;
    Expr d=null;
    ExprList el = new ExprList();
    ExprList named = new ExprList();
    NamedParam np = null;
    p = null;
    boolean has_named = false;
}
    : (
        ( t = test { el.add(t); } |
          np = named_param { named.add(np.name); named.add(np.value); has_named = true; }
        )
        (options {greedy=true;}:COMMA (
         t = test
         { el.add(t);
           if (has_named)
               throw new RecognitionException("Cannot have non-named parameter after named one");
         } |
          np = named_param { named.add(np.name); named.add(np.value); has_named = true; }
        ) )*
        ( COMMA
            ( STAR s = test (COMMA DOUBLESTAR d = test)?
          | DOUBLESTAR d = test
          )?
        )?
    |   STAR s = test (COMMA DOUBLESTAR d = test)?
    |   DOUBLESTAR d = test
    ) { p = new Parameters(el, named, s, d); }
    ;

/**
arglist: argument (options {greedy=true;}:COMMA argument)*
        ( COMMA
          ( STAR test (COMMA DOUBLESTAR test)?
          | DOUBLESTAR test
          )?
        )?
    |   STAR test (COMMA DOUBLESTAR test)?
    |   DOUBLESTAR test
    ;

argument : test (ASSIGN test)?
         ;
*/


list_iter [ Stmt inner ] returns [ Stmt s ]
{
    s = null;
}
    : s = list_for[inner]
	| s = list_if[inner]
	;

list_for [ Stmt inner ] returns [ ListForStmt s ]
{
    ExprList el, tl;
    s = null;
    Expr temp;
}
    : "for"
    {   temp = scope.name(NameTable.getIndex("" + ++temps));  }
    el = exprlist "in" tl = testlist (inner = list_iter[inner] )?
    {
        s = new ListForStmt(pack(el), pack(tl), temp);
        s.setBody(inner);
        temps--;
        return s;
    }
	;

list_if  [ Stmt inner ] returns [ Stmt s ]
{
    Expr t;
    s = null;
}
: "if" t =test  ( inner = list_iter[inner] )?
    {
        return new IfStmt(t, inner);
    }
	;

class PythonLexer extends Lexer;

options {
    k=3; // distinguish << and <<=
    testLiterals=false; // have to test in identifier rule
    charVocabulary='\u0003'..'\ufffe'; // all UNICODE range
}

{
/** Handles context-sensitive lexing of implicit line joining such as
 *  the case where newline is ignored in cases like this:
 *  a = [3,
 *       4]
 */
int implicitLineJoiningLevel = 0;
}

LPAREN	: '(' {implicitLineJoiningLevel++;} ;

RPAREN	: ')' {implicitLineJoiningLevel--;} ;

LBRACK	: '[' {implicitLineJoiningLevel++;} ;

RBRACK	: ']' {implicitLineJoiningLevel--;} ;

COLON 	: ':' ;

COMMA	: ',' ;

SEMI	: ';' ;

PLUS	: '+' ;

MINUS	: '-' ;

STAR	: '*' ;

SLASH	: '/' ;

VBAR	: '|' ;

AMPER	: '&' ;

LESS	: '<' ;

GREATER	: '>' ;

ASSIGN	: '=' ;

PERCENT	: '%' ;

AT : '@' ;

BACKQUOTE	: '`' ;

LCURLY	: '{' {implicitLineJoiningLevel++;} ;

RCURLY	: '}' {implicitLineJoiningLevel--;} ;

CIRCUMFLEX	: '^' ;

TILDE	: '~' ;

EQUAL	: "==" ;

NOTEQUAL	: "!=" ;

ALT_NOTEQUAL: "<>" ;

LESSEQUAL	: "<=" ;

LEFTSHIFT	: "<<" ;

GREATEREQUAL	: ">=" ;

RIGHTSHIFT	: ">>" ;

PLUSEQUAL	: "+=" ;

MINUSEQUAL	: "-=" ;

DOUBLESTAR	: "**" ;

STAREQUAL	: "*=" ;

DOUBLESLASH	: "//" ;

SLASHEQUAL	: "/=" ;

VBAREQUAL	: "|=" ;

PERCENTEQUAL	: "%=" ;

AMPEREQUAL	: "&=" ;

CIRCUMFLEXEQUAL	: "^=" ;

LEFTSHIFTEQUAL	: "<<=" ;

RIGHTSHIFTEQUAL	: ">>=" ;

DOUBLESTAREQUAL	: "**=" ;

DOUBLESLASHEQUAL	: "//=" ;

ARROW : "->" ;

QUESTION : "?" ;

DOLLAR : "$" ;

NUMBER
	:   // Hex
        '0' ('x' | 'X') ( '0' .. '9' | 'a' .. 'f' | 'A' .. 'F' )+
		('l' | 'L')?
        {$setType(INT);}

    |   // Octal
        '0' Int {$setType(INT);}
		(   FloatTrailer ('j' | 'J')? {$setType(COMPLEX);}
        |   ('l' | 'L')	{$setType(LONGINT);}
        )?

    |   '0' {$setType(INT);}
		(   (FloatTrailer) ('j' | 'J')? {$setType(COMPLEX);}
        |   ('j' | 'J') {$setType(COMPLEX);}
        |   ('l' | 'L')	{$setType(LONGINT);}
        )?

    |   // Int or float
        (	NonZeroDigit (Int)?
			(	('l' | 'L')	{$setType(LONGINT);}
			|	('j' | 'J')	{$setType(COMPLEX);}
			|	FloatTrailer ('j' | 'J')? {$setType(COMPLEX);}
			|	{$setType(INT);}
			)
		)
	|	'.' Int (Exponent)? ('j' | 'J')? {$setType(COMPLEX);}
    |   '.' {$setType(DOT);} // DOT (non number; e.g., field access)
	;

protected
Int : ( '0' .. '9' )+ ;

protected
NonZeroDigit : '1' .. '9' ;

protected
FloatTrailer
	:	'.'
	|	'.' Int (Exponent)?
	|   Exponent
	;

protected
Exponent
	:	('e' | 'E') ( '+' | '-' )? Int
	;

protected
Name
    :	( 'a' .. 'z' | 'A' .. 'Z' | '_')
        ( 'a' .. 'z' | 'A' .. 'Z' | '_' | '0' .. '9' )*
    ;

STRING_OR_NAME
options {
    testLiterals=true; // check to see if we are a keyword
}
{
    String prefix;
}
    :   String {$setType(STRING);}
    |   n:Name {prefix=n.getText().toUpperCase();}
        (   {prefix.equals("R")||prefix.equals("U")||prefix.equals("UR")}?
            String {$setType(STRING);}
        |   {$setType(NAME);}
        )
	;

/** Match various string types.  Note that greedy=false implies """
 *  should make us exit loop not continue.
 */
protected
String
options {
    // alts 1,3 and 2,4 are unnecessarily seen as ambiguous; turn off warning
    generateAmbigWarnings = false;
}
    :   "'''" (options {greedy=false;}:ESC|NEWLINE|.)* "'''"
	|   '"' '"' '"' (options {greedy=false;}:ESC|NEWLINE|.)* '"' '"' '"'
    |   '\'' (ESC|~('\\'|'\n'|'\''))* '\''
	|   '"' (ESC|~('\\'|'\n'|'"'))* '"'
	;

protected
ESC
	:	'\\' .
	;

/** Consume a newline and any whitespace at start of next line */
CONTINUED_LINE
	:	'\\' ('\r')? '\n' (' '|'\t')* { newline(); $setType(Token.SKIP); }
	;

/** Grab everything before a real symbol.  Then if newline, kill it
 *  as this is a blank line.  If whitespace followed by comment, kill it
 *  as it's a comment on a line by itself.
 *
 *  Ignore leading whitespace when nested in [..], (..), {..}.
 */
LEADING_WS
{
    int spaces = 0;
}
    :   {getColumn()==1}?
        // match spaces or tabs, tracking indentation count
        ( 	' '  { spaces++; }
        |	'\t' { spaces += 8; spaces -= (spaces % 8); }
        |   '\014' // formfeed is ok
        )+
        {
            if ( implicitLineJoiningLevel>0 ) {
                // ignore ws if nested
                $setType(Token.SKIP);
            }
            else {
                // make a string of n spaces where n is column number - 1
                char[] indentation = new char[spaces];
                for (int i=0; i<spaces; i++) {
                    indentation[i] = ' ';
                }
                String s = new String(indentation);
                $setText(s);
            }
        }

        // kill trailing newline or comment
        (   {implicitLineJoiningLevel==0}? ('\r')? '\n' {newline();}
            {$setType(Token.SKIP);}

        |   // if comment, then only thing on a line; kill so we
            // ignore totally also wack any following newlines as
            // they cannot be terminating a statement
            '#' (~'\n')* ('\n' {newline();})+
            {$setType(Token.SKIP);}
        )?
    ;

/** Comments not on line by themselves are turned into newlines because
    sometimes they are newlines like

    b = a # end of line comment

    or

    a = [1, # weird
         2]

    This rule is invoked directly by nextToken when the comment is in
    first column or when comment is on end of nonwhitespace line.

    The problem is that then we have lots of newlines heading to
    the parser.  To fix that, column==1 implies we should kill whole line.

    Consume any newlines following this comment as they are not statement
    terminators.  Don't let NEWLINE token handle them.
 */

COMMENT
{
    int startCol = getColumn();
}
    :   '#' (~'\n')* // let NEWLINE handle \n unless column = 1 for '#'
        { $setType(Token.SKIP); }
        ( {startCol==1}? ('\n' {newline();})+ )?
    ;

/** Treat a sequence of blank lines as a single blank line.  If
 *  nested within a (..), {..}, or [..], then ignore newlines.
 *  If the first newline starts in column one, they are to be ignored.
 */
NEWLINE
{
    int startCol = getColumn();
}
    :   (options{greedy=true;}:('\r')? '\n' {newline();})+
        {if (  implicitLineJoiningLevel>0 )
            $setType(Token.SKIP);
        }
    ;

WS  :   (' '|'\t')+ {$setType(Token.SKIP);}
    ;

